package com.leetcode.day8_2;

import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

/**
 * author: the_ring
 * Time: 2021/8/2 10:59
 * log: 网络延迟时间
 * link：https://leetcode-cn.com/problems/network-delay-time/
 */
public class Day4Code1 {
    public static void main(String[] args) {
        int[][] times = new int[][]{
                {1, 2, 1},
                {2, 1, 3}
        };
        int result = new Solution().networkDelayTime(times, 2, 2);
        System.out.println(result);
    }
}

class Solution {
    static int N = 110, INF = 0x3f3f3f3f;

    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] g = new int[N][N];
        int[] dist = new int[N];
        int edge = times.length;
        for (int i = 0; i < N; i++)
            Arrays.fill(g[i], INF);
        for (int i = 0; i < edge; i++) {
            int a = times[i][0], b = times[i][1], d = times[i][2];
            g[a][b] = Math.min(g[a][b], d);
        }
        return dijkstra(g, dist, k, n);
    }

    private int dijkstra(int[][] g, int[] dist, int k, int n) {
        Arrays.fill(dist, INF);
        dist[k] = 0;
        boolean[] st = new boolean[N];
        for (int i = 1; i <= n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }

        int cnt = 0, max = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] != INF) {
                cnt++;
                max = Math.max(max, dist[i]);
            }
        }
        if (cnt != n) return -1;
        return max;
    }
}

//class Solution {
//    public int networkDelayTime(int[][] times, int n, int k) {
//        int[][] path = new int[n][n];
//        for (int[] time : times) {
//            path[time[0] - 1][time[1] - 1] = time[2];
//        }
//        int[] temp = new int[n];
//        for (int i = 0; i < n; i++) {
//            if (i != k - 1) temp[i] = -1;
//        }
//        Stack<Integer> stack = new Stack<>();
//        stack.push(k - 1);
//        while (!stack.empty()) {
//            int top = stack.pop();
//            for (int i = 0; i < path[top].length; i++) {
//                if (path[top][i] != 0 && i != k - 1) {
//                    stack.push(i);
//                    if (temp[i] != -1 && temp[i] <= temp[top] + path[top][i])
//                        continue;
//                    temp[i] = temp[top] + path[top][i];
//                    path[top][i] = 0;
//                }
//            }
//        }
//        int delay = -1;
//        for (int i : temp) {
//            if (i == -1) return -1;
//            if (i > delay) delay = i;
//        }
//        return delay;
//    }
//}